package com.c2b.algorithm.leetcode.base;

import java.util.Arrays;

/**
 * <a href='https://leetcode.cn/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/description/'>切割后面积最大的蛋糕(Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts)</a>
 * <p>
 * 矩形蛋糕的高度为 h 且宽度为 w，给你两个整数数组 horizontalCuts 和 verticalCuts，其中：
 *     <ul>
 *         <li> horizontalCuts[i] 是从矩形蛋糕顶部到第  i 个水平切口的距离</li>
 *         <li> verticalCuts[j] 是从矩形蛋糕的左侧到第 j 个竖直切口的距离</li>
 *     </ul>
 * 请你按数组 horizontalCuts 和 verticalCuts 中提供的水平和竖直位置切割后，请你找出 面积最大 的那份蛋糕，并返回其 面积 。由于答案可能是一个很大的数字，因此需要将结果 对 (10^9 + 7) 取余 后返回。
 * </p>
 *
 * <p>
 *     <b>示例：</b>
 *     <pre>
 *         示例 1：
 *              输入：h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
 *              输出：4
 *
 *          示例 2：
 *              输入：h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
 *              输出：6
 *
 *          示例 3：
 *              输入：h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
 *              输出：9
 *     </pre>
 * </p>
 *
 * <p>
 *     <b>提示：</b>
 *     <ul>
 *         <li>2 <= h, w <= 10^9</li>
 *         <li>1 <= horizontalCuts.length <= min(h - 1, 10^5)</li>
 *         <li>1 <= verticalCuts.length <= min(w - 1, 10^5)</li>
 *         <li>1 <= horizontalCuts[i] < h</li>
 *         <li>1 <= verticalCuts[i] < w</li>
 *         <li>题目数据保证 horizontalCuts 中的所有元素各不相同</li>
 *         <li>题目数据保证 verticalCuts 中的所有元素各不相同</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/27 10:10
 */
public class LC1465MaximumAreaOfPieceOfCake_M {
    static class Solution {

        public int maxArea(int h, int w, int[] horizontalCuts, int[] verticalCuts) {
            long maxHeight = 0;
            Arrays.sort(horizontalCuts);
            int pre = 0;
            for (int horizontalCut : horizontalCuts) {
                maxHeight = Math.max(horizontalCut - pre, maxHeight);
                pre = horizontalCut;
            }
            maxHeight = Math.max(h - pre, maxHeight);

            long maxWeight = 0;
            Arrays.sort(verticalCuts);
            pre = 0;
            for (int verticalCut : verticalCuts) {
                maxWeight = Math.max(verticalCut - pre, maxWeight);
                pre = verticalCut;
            }
            maxWeight = Math.max(w - pre, maxWeight);

            return (int) ((maxHeight * maxWeight) % 1000000007);
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxArea(5, 4, new int[]{1, 2, 4}, new int[]{1, 3}));
        System.out.println(solution.maxArea(5, 4, new int[]{3, 1}, new int[]{1}));
        System.out.println(solution.maxArea(5, 4, new int[]{3}, new int[]{3}));
        System.out.println(999999996000000004L);
        System.out.println(1000000007);
        System.out.println((int) (999999996000000004L%1000000007));
        System.out.println(solution.maxArea(1000000000, 1000000000, new int[]{2}, new int[]{2}));


    }
}
